package com.cg.leetcode;

import org.junit.Test;

import java.util.Arrays;

/**
 * 1658.将 x 减到 0 的最小操作数
 *
 * @author cg
 * @create 2022-12-20
 **/
public class LeetCode_1658 {

    @Test
    public void test1658() {
        System.out.println(minOperations(new int[]{1, 1, 4, 2, 3}, 5));
        System.out.println(minOperations(new int[]{5, 6, 7, 8, 9}, 4));
        System.out.println(minOperations(new int[]{3, 2, 20, 1, 1, 3}, 10));
    }

    /**
     * 给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。
     * 如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。
     * <p>
     * 示例 1：
     * 输入：nums = [1,1,4,2,3], x = 5
     * 输出：2
     * 解释：最佳解决方案是移除后两个元素，将 x 减到 0 。
     * <p>
     * 示例 2：
     * 输入：nums = [5,6,7,8,9], x = 4
     * 输出：-1
     * <p>
     * 示例 3：
     * 输入：nums = [3,2,20,1,1,3], x = 10
     * 输出：5
     * 解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。
     * <p>
     * 提示：
     * 1 <= nums.length <= 10^5
     * 1 <= nums[i] <= 10^4
     * 1 <= x <= 10^9
     *
     * @param nums
     * @param x
     * @return
     */
    public int minOperations(int[] nums, int x) {
        int left = 0, right = 0;
        int sum = Arrays.stream(nums).sum();
        int currentSum = 0;
        int maxLength = -1;
        int count = sum - x;
        if (count < 0) {
            return maxLength;
        }
        while (right < nums.length) {
            currentSum += nums[right++];
            while (currentSum > count) {
                currentSum -= nums[left++];
            }
            if (currentSum == count) {
                maxLength = Math.max(maxLength, right - left);
            }
        }
        return maxLength == -1 ? -1 : nums.length - maxLength;
    }

}
